package sword_offer;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @class Code46
 * @description 剑指 Offer 44. 数字序列中某一位的数字
 * 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
 *
 * 请写一个函数，求任意第n位对应的数字。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：3
 * 示例 2：
 *
 * 输入：n = 11
 * 输出：0
 *  
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-09 10:45
 */
public class Code46 {

    public static void main(String[] args) {
        System.out.println(findNthDigit(1000000000));
    }

    public static int findNthDigit(int n) {
        if (n == 0) {
            return 0;
        }
        int digit = 1;
        long left = 1, right = 9 * (long)Math.pow(10, (digit - 1)) * digit;
        while (n > right) {
            digit++;
            left = right + 1;
            right += 9 * (long)Math.pow(10, (digit - 1)) * digit;
        }
        long x = (n - left) / digit + (long) Math.pow(10, (digit - 1)); // 对应哪个数字
        return String.valueOf(x).charAt((int) ((n - left) % digit)) - '0';
    }
}
/*
找规律
首先找到以下规律
数字      第几位     位数
1~9      1~9        1
10~99    10~189     2
100~999  190~2889   3
然后给你一个位数n首先判断这个数字它在几和几之间，然后去判断这个位数对应的数字是这个范围内的第几个数，最后判断这个位数是这个数的第几位
巨难推，我是垃圾
 */